package org.chnxi.leetcode.problems.ques4;

/**
 * 寻找两个正序数组的中位数-按照查找的下标逐一增长
 * 执行用时 :3 ms, 在所有 Java 提交中击败了61.83%的用户
 * 内存消耗 :40.5 MB, 在所有 Java 提交中击败了100.00%的用户
 */
public class Simple1 {

    public static void main(String[] args) {
        int[] num0_1 = {1,3};
        int[] num0_2 = {2};

        int[] num1_1 = {1,1,1,1,1,1,1,6,7,8};
        int[] num1_2 = {2,3,4,5};

        System.out.println(findMedianSortedArrays(num0_1 , num0_2));

    }

    public static double findMedianSortedArrays(int[] num1 , int[] num2){
        int num1Len = num1.length;
        int num2Len = num2.length;
        int midIdx = (num1Len+num2Len) /2;
        if( (num1Len + num2Len) % 2 == 0){
            int left = getIndexNum(num1, num2, midIdx-1);
            int right = getIndexNum(num1, num2, midIdx);
            return (double) (left+right)/2;
        }else{
            return (double)getIndexNum(num1, num2, midIdx);
        }
    }

    public static int getIndexNum(int[] num1, int[] num2, int idx){
        int num1Len = num1.length;
        int num2Len = num2.length;

        int num1Idx = 0;
        int num2Idx = 0;

        int step = 0;

        int num1Tmp = Integer.MAX_VALUE;
        int num2Tmp = Integer.MAX_VALUE;

        while (step <= idx){

            num1Tmp = num1Idx < num1Len ? num1[num1Idx] : Integer.MAX_VALUE;
            num2Tmp = num2Idx < num2Len ? num2[num2Idx] : Integer.MAX_VALUE;

            if(num1Tmp < num2Tmp){
                num1Idx++;
            }else{
                num2Idx++;
            }
            step++;
        }
        return Math.min(num1Tmp , num2Tmp);
    }
}
